The intracellular concentration of diadenosine tetraphospate (Ap4A) increases upon exposure to stress conditions. Despite being discovered over 50 years ago, the cellular functions of Ap4A are still enigmatic. If and how the varied Ap4A is a signal and involved in the signaling pathways leading to an appropriate cellular response remain to be discovered. Because the turnover of Ap4A by Ap4A cleaving enzymes is rapid, small molecule inhibitors for these enzymes would provide tools for the more detailed study of the role of Ap4A. Here, we describe the development of a high-throughput screening assay based on a fluorogenic Ap4A substrate for the identification and optimization of small molecule inhibitors for Ap4A cleaving enzymes. As proof-of-concept we screened a library of over 42 000 compounds toward their inhibitory activity against the Ap4A phosphorylase (Rv2613c) of Mycobacterium tuberculosis (Mtb). A sulfanylacrylonitril derivative with an IC50 of 260 ± 50 nM in vitro was identified. Multiple derivatives were synthesized to further optimize their properties with respect to their in vitro IC50 values and their cytotoxicity against human cells (HeLa). In addition, we selected two hits to study their antimycobacterial activity against virulent Mtb to show that they might be candidates for further development of antimycobacterial agents against multidrug-resistant Mtb.